/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/guess-number-higher-or-lower
   @Language: C++
   @Datetime: 19-04-26 16:50
   */

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
	/**
	 * @param n an integer
	 * @return the number you guess
	 */
	int guessNumber(int n) {
		// Write your code here
		for(int i=1, mid=1+(n-1)/2; i<=n;){
			switch (guess(mid)){
				case 1 : i=mid+1, mid=i+(n-i)/2; break;
				case -1: n=mid-1, mid=i+(n-i)/2; break;
				case 0 : return mid;
			}
		}
		return 0;
	}
};
